The scalability of routing impacts many systems in many application scenarios. The exponential growth of the BGP routing table has been a growing concern, and several schemes have been proposed to address this problem.
One proposed solution to this scalability problem has been to assist Internet Protocol (IP) routing with some geographic routing. For other systems such as ad hoc networks, which, unlike IP networks, have no universally known global addresses, geometric (or geographic) routing can also enhance the scalability of the routing.
Greedy forwarding is also well-known and requires very little routing state: a packet is forwarded to a destination point based on the relative distance of this point with that of the neighbors of the node holding the packet. More specifically, in greedy forwarding, a packet is forwarded to the node which minimizes the distance to the destination. Each node thus is only required to know the position of its neighbors to forward packets and the size of the routing table is proportional to the degree of the node. Such routing is both local, and memoryless.
Geometric routing based on the actual location of the nodes requires accurate knowledge of the node's location. Further, the physical location of the nodes might not coincide with the connectivity of the network. To take advantage of the network topology, it has been proposed to build virtual (geographic) coordinates on top of the graph created by the network connectivity. Greedy routing is then performed on these virtual coordinates.
Kleinberg, in “Geographic Routing Using Hyperbolic Space,” in Proceedings of IEEE Infocom, 2007, showed how to construct a greedy embedding onto the 2-dimensional hyperbolic plane. This does not however solve the issue of scalability, since the coordinates in the hyperbolic plane in Kleinberg's scheme require n bits to describe the location of one node, where n is the number of nodes in the network. This implies that, even though the number of entries in the route table is scalable, the size of each entry is not.